def count_sort(array=[]):
    if array is not None and len(array) != 0:
        # 找出数列中最大值，开辟数组空间
        max_value = array[0]
        for i in range(1, len(array)):
            if max_value < array[i]:
                max_value = array[i]
        # 根据数列最大值，开辟数据存储数据
        count_array = [0] * (max_value + 1)
        # 遍历数组，填充计数
        for i in range(len(array)):
            count_array[array[i]] += 1
        # 遍历计数数组，输出排序结果
        sorted_array = []
        for i in range(len(count_array)):
            for j in range(count_array[i]):
                sorted_array.append(i)
        return sorted_array


def count_sort_v2(array=[]):
    if array is not None and len(array) != 0:
        # 找出最大值和最小值
        max_value = array[0]
        min_value = array[0]
        for i in range(len(array)):
            if array[i] > max_value:
                max_value = array[i]
            if array[i] < min_value:
                min_value = array[i]
        d = max_value - min_value
        # 计数数组
        count_array = [0] * (d + 1)
        for i in range(len(array)):
            count_array[array[i] - min_value] += 1
        for i in range(1, len(count_array)):
            count_array[i] += count_array[i - 1]
        print(count_array)
        sorted_array = [0] * len(array)
        for i in range(len(array) - 1, -1, -1):
            sorted_array[count_array[array[i] - min_value] - 1] = array[i]
            count_array[array[i] - min_value] -= 1
        return sorted_array
    else:
        return None


if __name__ == '__main__':
    # sorted_array = count_sort(list([9, 2, 3, 4, 2, 4, 5, 2, 1, 7, 6, 3, 7, 0, 10, 2, 3, 4, 5, 6, 7, 8, 9, 10]))
    # print(sorted_array)
    array = list([90, 95, 99, 94, 98, 95])
    print(count_sort_v2(array))
